package com.yiwenup.sorting._05_merge;

import com.yiwenup.sorting.base.Sort;

/**
 * 归并排序
 * 时间复杂度：最好 - O(nlogn)；最坏 - O(nlogn)；平均复杂度 - O(nlogn)
 * 空间复杂度：O(n)
 * 稳定性：稳定
 **/
@SuppressWarnings("unchecked")
public class MergeSort<E extends Comparable<E>> extends Sort<E> {

    private E[] leftPart;

    @Override
    protected void work() {
        leftPart = (E[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    /**
     * 构造递归方法
     * <p>
     * 提供 [begin, end) 范围的归并递归调用
     */
    private void sort(int begin, int end) {
        // 元素个数
        if (end - begin < 2) return;

        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }

    /**
     * 将 [begin,mid) 和 [mid, end) 合并成一个有序子序列
     */
    private void merge(int begin, int mid, int end) {
        // 左边数组区间
        int lb = 0, le = mid - begin;
        // 右边数组区间
        int rb = mid, re = end;
        // 将要覆盖的位置索引
        int cover = begin;

        // 备份出左边部分的数组，以达到 merge 操作还是在本数组中
        for (int i = lb; i < le; i++) {
            leftPart[i] = array[begin + i];
        }

        // 合并操作
        // 左边提前遍历完，则结束
        while (lb < le) {
            if (rb < re && cmp(array[rb], leftPart[lb]) < 0) {
                array[cover++] = array[rb++];
            } else {
                array[cover++] = leftPart[lb++];
            }
        }
    }
}
